\documentclass[a4]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage{fancyhdr}
\usepackage{verbatim}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{gastex}
\usepackage{hyperref}
\usepackage{float}

\lhead{Projet de flots et combinatoires}

\begin{document}

	% Page de garde
	\begin{figure}[t]
		\begin{center}
			\includegraphics[scale=0.4]{logo.jpg}
		\end{center}
	\end{figure}
	\title{\Large{\textbf{Projet de problèmes combinatoires et routage}}\\\Huge{\textbf{Optimisation du cout de production d'électricité en France}}}
	\author{%\textbf{Réalisateurs} 
	Antoine Bizac \and Abdessamad Hailass \and Kahina Bourenane \and Mehdi Haddoun \and Salma El Mohib \and Papa Gueye \and Emmanuel Julien \and Maxime Blanchemain \and Dehia Aitferhat  \\
	\\
	}
	\date{\today}
	
	\maketitle % affiche le titre et les auteurs
        \newpage
	% Sommaire
	\tableofcontents{}
	\newpage
	
	% Include des différentes parties
	\section{Présentation du problème}
	Le projet a pour objectif d'envisager par une approche formelle la répartition d'électricité en France. Nous nous 		placerons du point de vue fournisseur d'électricité qui cherche à minimiser son cout global de production 		électrique tout en honorant son devoir d'approvisionnement des clients.
	\subsection{Modélisation}
	\subsubsection{Données}	
	\begin{itemize}
	\item Soit i appartenant à [1,n] un site du réseau électrique français (P). 
	\item Soit j appartenant à [1,l] un client alimenté par le réseau (C).
	\item Soit (Pn,max(i) , Pn,min(i)) la puissance maximale et minimale de chaque site i.
	\item On considérera Bj le besoin de chaque client j.
	\item Ci le cout de production  d'un MWh par le site i.
	\item Soit dij la distance entre le site i et le client j.
	\item Soit aij la distance entre le site i et le client j.
	\item On considérera la tension U = 400KV si le site de production du réseau et le client alimenté par le réseau ne 		sont pas dans la même région et U = 90 KV sinon.
	\item La puissance P = 3.10-8.
	\item S = 500 m2.
	\item I = 400 A.
	\item aij = 1 -(Rij.L)/U
	\item Rij = p.aij
	\end{itemize}
	\subsubsection{Variable de décision}
	\begin{itemize}
	\item Xij : la quantité d'énergie en MWh produite par le site i destiné au client j.
	\end{itemize}	
	\subsection{La fonction objectif}
	\\ Min \Sigma i \Sigma j Ci.Xij 
	\section{Contraintes}
	\forall  1 \le i \le n : Pn min(i) \le \Sigma j Xij \le Pn max(i) \\  ou \\   \Sigma j  Xij =0
	\forall 1 \le j \le L :\Sigma j \Alpha ij.Xij \ge Bj 

        \section{Remarque générale sur l'implémentation}
        Pour l'implémentation, nous avons décidé d'utiliser le langage python afin de bénéficier des bibliothèques graphiques tels que NetworkX ou des fonctions de haut niveau pour la résolution de programme linéaire, tels que fmin-cobyla du package scipy.optimize ou Minimize de scipy.optimize, bien que, comme nous l'expliquerons plus loin, le jeu de donnée ait été trop conséquent pour obtenir des résultats satisfaisant avec ces deux fonctions.
        En outre, nous avons fait une implémentation de notre programme sous le Solver d'IBM  Cplex afin de pouvoir comparer les résultats obtenues avec le véritable optimum.
        \section{Resolution avec Simplex, programmation linéaire pure}
        Nous avons utilisé le Cplex d'IBM pour résoudre ce problème, ce dernier n'étant plus disponible à l'ENSEIRB,nous avons dûs nous rendre au Cremi pour l'utiliser. La résolution linéaire du problème nous donne :\\
\textbf{Min} $ \displaystyle { \sum_{i}^{}} {\sum_{j}} C_ix_{ij} = 5614500,0000$.\\
Ce résultat nous permettra de comparer les résultats des algorithmes d'approximations que nous allons implenter en python. De plus, nous pourrons générer une première carte d'attribution avec le tableau des x_i,_j trouvé à l'aide de la bibliothèque de networkX.
%Si prêt à temps donner la matrice des x_ij !



	\section{Passage du linéaire au combinatoire}
        \paragraph{Présentation du problème combinatoire}\\
	Le problème obtenu est linéaire et résolvable en simplexe pour avoir une solution optimale.\\
	Pour avoir un algorithme d'approximation, on le transforme sous un problème de SET COVER avec le programme linéaire 		suivant : On prendra Xi comme une variable de décision  telle que : Xij = 1 si on prend l'ensemble Si; Xi = 0 sinon.	\\
	 
	PL :\\
	\\	
		min \Sigma C(Si).Xi \\
		\forall j\in C, \Sigma Xi \le 1\\
		Xi \in \left\{0, 1\right\}	\\
	 
	En relaxant le problème on obtient : \\			
	PL relaxé : \\
	\\
		min \Sigma C(Si).Xi \\
		\forall j\in C, \Sigma Xi \le 1\\
		0 \le Xi \le 1	\\
                
                \paragraph{Générations des Sets}\\
                Nous avons selon deux méthodes, implémentés sous les non de:\\
                generateSetSimplified()\\
                generateSetPerso()\\
                Les deux méthodes reposent sur une distance critique D:\\
                $D=\max(\min_{Producteur   p,Client   c }d(p,c))$. 
                
                La première génère card(Produteurs) sets. Elle génère un set par producteur, englobant l'ensemble des clients dont la distance au producteur est inférieure à D.\\
                La Deuxième génère !card(Produteurs) sets. Pour chaque Producteur, elle  englobant l'ensemble des clients dont la distance au producteur est inférieure à D. Puis elle trouve le Client le plus éloigné par la distance H, génère un Set avec l'ensemble des Client de la liste  dont la distance avec le producteur est inférieure à H, puis retire le Client de la liste des Clients associées au producteur. Et ainsi dessuite.
                                
        \section{Première résolution par algorithme Glouton}
        Nous avons implémentés l'algorithme glouton vue dans le cours pour résoudre ce problème. Vous pourrez le tester en executant le programme TestGreedy.py depuis l'archive.

	\section{Deuxième résolution avec le SET COVER utilisant la relaxation linéaire}
	\subsection{Présentation de l'algorithme}\\
	Etapes de résolution (Algorithme du SET COVER)
	\begin{itemize}
	\item On résoud le problème linéaire avec le simplex pour obtenir la solution optimale Xi*.
	\item On prend Si avec une probabilité  : min(len(n).Xi*, 1)
	\item \forall j \in C 
	non couvert, ajouter Si de cout minimum qui couvrira j.
	\end{itemize}				
        
        \subsection{Implémentation de l'algorithme}\\
        Pour la partie de résolution du problème relaxé, il faut résoudre un problème de programmation linéaire. Idéalement, la fonction à utilisée s'appelle minimize, du package scipy.optimize. Cette fonction code plus ou moins l'algorithme du simplex, et devrait supporter un gros jeu de données. Le seul problème, c'est qu'elle n'a pas encore été publiée!! D'après les développeurs, elle devrait l'être d'ici fin Mai 2012. Nous avons laissés pour mémoire en commentaire la fonction linearRelaxation() dans FonctionSetCover. Il sera alors intéressant, fin Mai, de la tester.
        En attendant, il nous fallait une fonction provisoire. Problème, il n'existe pas de fonction de minimisation actuellement, qui peut supporter des contraintes multiples (c'est tout l'objet du développement de minimize!!).\\
        Nous avons donc utilisé la fonction qui s'en rapproché le plus, fmincobyla, sur la version 10.1 de scipy, et avons modifiés sont code source pour qu'elle supporte plusieurs fonction de contraintes prenant plusieur argument. Nous avons d'ailleurs transmis aux développeurs de scipy ce développement.\\
        Cette solution a marché pour des petits jeux de données, mais n'est malheureusement pas passée pour notre jeu de test réel. C'est sans doute qu'elle n'est pas réellement fait pour le supporter. Il nous reste donc à attendre fin Mai!\\
        
        

        \section{Répartition travail}
        Papa Magueye, implémentation jeux de données pour test python.\\
        Dehia Fahrat, ressources jeux de donnée.\\
        Emmanuel Julien, résolution solver.\\
        Antoine Bizac, résolution solver.\\
        Salma Elmohib, rapport.\\
        Abdessamad Hailass, interfacage python de la  solution avec networkX.\\
        Mehdi Haddoun,interfacage python de la  solution avec networkX.\\
        Bourenane Kahina, rapport+présentation.\\
        Maxime Blanchemain, résolution problème, code python algorithme, test, organisation et rapport.\\
       
	\section{Conclusion}
	Il est un peu regrettable que nous ayons été bloqués avec la relaxation linéaire en python, mais pour le reste, les deux algorithmes tournent. Ce problème, qui provient d'un sujet de stage d'EDF, est assez minimalisé ici, il serait intéressant d'introduire des données aléatoires, par exemple, des consommations des clients non constantes, pour se rapprocher de la problématique réelle.	
\end{document}
